﻿//690. 员工的重要性
//你有一个保存员工信息的数据结构，它包含了员工唯一的 id ，重要度和直系下属的 id 。
//给定一个员工数组 employees，其中：
//employees[i].id 是第 i 个员工的 ID。
//employees[i].importance 是第 i 个员工的重要度。
//employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。
//给定一个整数 id 表示一个员工的 ID，返回这个员工和他所有下属的重要度的 总和。

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    unordered_map<int, int>  hash;   // id 标号

    void dfs(vector<Employee*> employees, int id, int& ret)
    {
        int index = hash[id];
        ret += employees[index]->importance;
        //递归
        vector<int> sub = employees[index]->subordinates;
        int n = sub.size();
        for (int i = 0; i < n; i++)
        {
            dfs(employees, sub[i], ret);
        }
    }

    int getImportance(vector<Employee*> employees, int id)
    {
        int ret = 0;
        int n = employees.size();
        for (int i = 0; i < n; i++)
        {
            hash.insert({ employees[i]->id , i });
        }
        dfs(employees, id, ret);
        return ret;
    }
};